#-*- coding: utf-8 -*-

def modexp(a, b, m):
	res = 1
	print "res=%d" % res
	while b>0:
		print "base=%4d\texp=%4d\tres=%4d\t%s" % \
			(a, b, res, ("impair->nv_res" if b % 2 else "pair"))
		if b % 2: #impair
			res = (res * a) % m
		b /= 2 #idiv
		a = (a * a) % m
	print "res=%d" % res
	return res

def test(a, b, m):
	return pow(a, b, m) == modexp(a, b, m)


test(3, 25, 1037)
